package main

import (
	"fmt"
)

const TEST_SIZE = 10000000
const TEST_MAX_VALUE = 1000000000

func GenerateTestVec() []uint32 {
	test_vec := []uint32{}
	rand := uint64(0)

	for i := 0; i < TEST_SIZE; i++ {
		test_vec = append(test_vec, uint32(rand))
		rand *= 131313131
		rand += 13131
		rand %= TEST_MAX_VALUE
	}
	return test_vec
}

func ComputeOutputHash(testVec []uint32) uint32 {
	hash := uint64(len(testVec))
	for _, v := range testVec {
		hash = (hash*131313131 + uint64(v)) % TEST_MAX_VALUE
	}
	return uint32(hash)
}

func MyMergeSort(elements []uint32) {
	if len(elements) > 1 {
		mid := len(elements) / 2
		sub_elements1 := append([]uint32{}, elements[:mid]...)
		sub_elements2 := append([]uint32{}, elements[mid:]...)

		MyMergeSort(sub_elements1)
		MyMergeSort(sub_elements2)

		element_len := len(elements)
		sub_len1 := len(sub_elements1)
		sub_len2 := len(sub_elements2)
		for sub_len1 > 0 && sub_len2 > 0 {
			element_len -= 1
			if sub_elements1[sub_len1-1] < sub_elements2[sub_len2-1] {
				sub_len2 -= 1
				elements[element_len] = sub_elements2[sub_len2]
			} else {
				sub_len1 -= 1
				elements[element_len] = sub_elements1[sub_len1]
			}
		}
		copy(elements, sub_elements1[:sub_len1])
		copy(elements, sub_elements2[:sub_len2])
	}
}

func main() {
	var test_vec []uint32 = GenerateTestVec()
	MyMergeSort(test_vec)
	fmt.Println(ComputeOutputHash(test_vec))
}
